/*
 * p562.cpp
 *
 *  Created on: 2013-3-14
 *      Author: zy
 */

#include<cstdio>
#include<cstring>
const int maxn=50010;
int dp[maxn],v[101];
int main()
{
	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		int s=0,sum;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&v[i]);
			s+=v[i];
		}
		sum=s;
		s/=2;
		for(int i=1;i<=n;i++)
			for(int j=s;j>=0;j--)
				if(j>=v[i]&&dp[j-v[i]]+v[i]>dp[j])
					dp[j]=dp[j-v[i]]+v[i];
		printf("%d\n",sum-2*dp[s]);
	}
	return 0;
}

